#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

struct ListNode
{
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
	ListNode* dummynode = new ListNode(0);
	ListNode* tail = dummynode;

	while (list1 && list2)
	{
		if (list1->val <= list2->val)
		{
			tail->next = list1;
			tail = tail->next;
			list1 = list1->next;
		}
		else
		{
			tail->next = list2;
			tail = tail->next;
			list2 = list2->next;
		}
	}

	while (list1)
	{
		tail->next = list1;
		tail = tail->next;
		list1 = list1->next;
	}
	while (list2)
	{
		tail->next = list2;
		tail = tail->next;
		list2 = list2->next;
	}

	return dummynode->next;
}



//vector<int> sortedSquares(vector<int>& nums)
//{
//	vector<int> res(nums.size());
//	int begin = 0, end = nums.size() - 1;
//	int i = nums.size() - 1;
//	while (begin < end)
//	{
//		nums[begin] = abs(nums[begin]);
//		nums[end] = abs(nums[end]);
//
//		if (nums[begin] > nums[end])
//		{
//			res[i--] = nums[begin] * nums[begin];
//			begin++;
//		}
//		else
//		{
//			res[i--] = nums[end] * nums[end];
//			end--;
//		}
//	}
//	return res;
//}

//vector<int> sortedSquares(vector<int>& nums)
//{
//	vector<int> res(nums.size());
//	int begin = 0, end = nums.size() - 1;
//	int i = nums.size() - 1;
//	while (begin < end)
//	{
//		nums[begin] = abs(nums[begin]);
//		nums[end] = abs(nums[end]);
//
//		if (nums[begin] > nums[end])
//		{
//			res[i--] = nums[begin] * nums[begin];
//			begin++;
//		}
//		else
//		{
//			res[i--] = nums[end] * nums[end];
//			end--;
//		}
//	}
//	return res;
//}

int main()
{
	vector<int> v{ -7,-3,2,3,11 };
	sortedSquares(v);
	return 0;
}

//void print(vector<int>& nums,int i)
//{
//	if (i == nums.size())
//	{
//		return;
//	}
//	cout << nums[i] << " ";
//	print(nums, i + 1);
//}
//
//int main()
//{
//	vector<int> nums{ 1,2,3,4,5,6,7,8,9 };
//	//for (int i = 0; i < nums.size(); i++)
//	//{
//	//	cout << nums[i] << " ";
//	//}
//	print(nums,0);
//	return 0;
//}


//using namespace std;
//
//struct TreeNode
//{
//    int val;
//    TreeNode* left;
//    TreeNode* right;
//    TreeNode() : val(0), left(nullptr), right(nullptr) {}
//    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
//};
//
//bool _isSymmetric(TreeNode* rootleft, TreeNode* rootright)
//{
//    if (rootleft->left == nullptr && rootleft->right==nullptr 
//        && rootright->left==nullptr &&rootright->right == nullptr)
//    {
//        return true;
//    }
//    if (rootleft->left == nullptr && rootright->right != nullptr)
//    {
//        return false;
//    }
//    if (rootleft->right == nullptr && rootright->left != nullptr)
//    {
//        return false;
//    }
//    if (rootleft->left->val != rootright->right->val)
//    {
//        return false;
//    }
//    if (rootleft->right->val != rootright->left->val)
//    {
//        return false;
//    }
//    return _isSymmetric(rootleft->left, rootright->right) && _isSymmetric(rootleft->right, rootright->left);
//}
//
//bool isSymmetric(TreeNode* root)
//{
//    if (root == nullptr)
//    {
//        return true;
//    }
//    if (root->left == nullptr && root->right == nullptr)
//    {
//        return true;
//    }
//    if (root->left == nullptr || root->right == nullptr)
//    {
//        return false;
//    }
//    return _isSymmetric(root->left, root->right);
//}
//
//int main()
//{
//	vector<int> nums{ 1,2,2,3,3 };
//	int i = 0;
//	TreeNode* n1 = new TreeNode(nums[i++]);
//	TreeNode* n2 = new TreeNode(nums[i++]);
//	TreeNode* n3 = new TreeNode(nums[i++]);
//	TreeNode* n4 = new TreeNode(nums[i++]);
//	TreeNode* n5 = new TreeNode(nums[i++]);
//	//TreeNode* n6 = new TreeNode(nums[i++]);
//	//TreeNode* n7 = new TreeNode(nums[i++]);
//
//	n1->left = n2;
//	n1->right = n3;
//
//	n2->left = nullptr;
//	n2->right = n4;
//
//	n3->left = n5;
//	n3->right = nullptr;
//
//    cout << isSymmetric(n1) << endl;
//
//    return 0;
//}